package leetcode;

/**
 * 分割等和子集
 */
public class Solution44 {
    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        final boolean b = canPartition(nums);
        System.out.println(b);
    }

    public static boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int len = nums.length;
        int sum = 0;
        for (int sums : nums) {
            sum = sum + sums;
        }
        //奇数不可分割
        if (sum % 2 != 0) {
            return false;
        }
        //判断是否可以分割
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < len; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            if (dp[target] == target) {
                return true;
            }
        }
        return dp[target] == target;
    }

}
